package 力扣_树算法.搜索树;


import java.util.*;

/**501. 二叉搜索树中的众数
 * @author zx
 * @create 2022-04-15 19:25
 */
public class    Num501 {
    /**
     以下思想来自代码随想录：
     遍历有序数组的元素出现频率(从头遍历),那么一定是相邻两个元素作比较;在树上怎么搞呢？
     需要弄一个指针指向前一个节点,这样每次cur(当前节点)才能和 prev(前一个节点)作比较。
     而且初始化的时候prev = NULL,这样当prev为NULL时候,我们就知道这是比较的第一个元素,然后再给prev赋值即prev = cur
     此时又有问题了,因为要求最大频率的元素集合,直观想的想法是要先遍历一遍找出频率最大的次数maxCount，
     然后在重新遍历一遍再把出现频率为maxCount 的元素放进集合。
     那么如何只遍历一遍呢？
     如果频率count等于maxCount,当然要把这个元素加入到结果集中(以下代码为res数组)时感觉这里有问题，
     res怎么能轻易就把元素放进去了呢，万一，这个 maxCount 此时还不是真正最大值呢。
     所以下面要做如下操作：
     频率 count 大于 maxCount 的时候，不仅要更新 maxCount，而且要清空结果集（以下代码为 res数组），
     因为结果集之前的元素都失效了。
     */
    List<Integer> list = new ArrayList<>();
    int count = 0;
    int maxCount = Integer.MIN_VALUE;
    TreeNode prev = null;
    public int[] findMode(TreeNode root) {
        inOrder(root);
        int[] res = new int[list.size()];
        for(int i = 0;i < list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        if(prev != null && root.val == prev.val){//与前一个节点数值相同
            count++;
        }else{//与前一个节点数值不同
            count = 1;
        }
        if(count == maxCount){//如果和最大值相同,放进list中
            list.add(root.val);
        }
        if(count > maxCount){//如果计数大于最大值
            maxCount = count;
            list.clear();//关键：清空list,之前list里的元素都失效了
            list.add(root.val);
        }
        prev = root;//更新prev
        inOrder(root.right);
    }
}
